{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ca6b70d1",
   "metadata": {},
   "source": [
    "# 1. deque的基本概念\n",
    "deque （双端队列，double-ended queue的缩写）是一种可以在两端高效添加和删除元素的线性数据结构。它的特点是：\n",
    "\n",
    "- 两端操作的时间复杂度都是O(1)\n",
    "- 内存使用高效\n",
    "- 提供了丰富的操作方法"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58e30ce8",
   "metadata": {},
   "source": [
    "# 2. 创建deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f5e0a8d3",
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m运行具有“.venv (3.13.5) (Python 3.13.5)”的单元格需要ipykernel包。\n",
      "\u001b[1;31m将“ipykernel”安装到 Python 环境中。\n",
      "\u001b[1;31m命令:“d:/Documents/PyCode/.venv/Scripts/python.exe -m pip install ipykernel -U --force-reinstall”"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "# 创建空deque\n",
    "dq1 = deque()\n",
    "\n",
    "# 从列表创建\n",
    "dq2 = deque(['a', 'b', 'c'])\n",
    "\n",
    "# 从字符串创建\n",
    "dq3 = deque(\"hello\")\n",
    "\n",
    "# 指定最大长度\n",
    "dq4 = deque([1, 2, 3], maxlen=5)  # 限制deque最多只能有5个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53dc36e2",
   "metadata": {},
   "source": [
    "# 3. 基本操作方法\n",
    "## 3.1 添加元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "175cdde1",
   "metadata": {},
   "outputs": [],
   "source": [
    "dq = deque([1, 2, 3])\n",
    "\n",
    "# 在右侧（尾部）添加单个元素\n",
    "dq.append(4)            # deque([1, 2, 3, 4])\n",
    "\n",
    "# 在左侧（头部）添加单个元素\n",
    "dq.appendleft(0)        # deque([0, 1, 2, 3, 4])\n",
    "\n",
    "# 在右侧添加多个元素\n",
    "dq.extend([5, 6, 7])    # deque([0, 1, 2, 3, 4, 5, 6, 7])\n",
    "\n",
    "# 在左侧添加多个元素\n",
    "dq.extendleft([-1, -2]) # deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "778a6722",
   "metadata": {},
   "source": [
    "## 3.2 删除元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "3ee60e06",
   "metadata": {},
   "outputs": [],
   "source": [
    "dq = deque([0, 1, 2, 3, 4])\n",
    "\n",
    "# 从右侧删除元素并返回\n",
    "dq.pop()               # 返回4，deque变为[0, 1, 2, 3]\n",
    "\n",
    "# 从左侧删除元素并返回\n",
    "dq.popleft()           # 返回0，deque变为[1, 2, 3]\n",
    "\n",
    "# 删除指定值的第一个匹配项\n",
    "dq.remove(2)           # deque变为[1, 3]\n",
    "\n",
    "# 清空deque\n",
    "dq.clear()             # deque变为[]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73a5f0c8",
   "metadata": {},
   "source": [
    "## 3.3 其他常用操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "b4084749",
   "metadata": {},
   "outputs": [],
   "source": [
    "dq = deque([1, 2, 3, 4, 5])\n",
    "\n",
    "# 获取元素数量\n",
    "len(dq)                # 返回5\n",
    "\n",
    "# 访问元素（支持索引）\n",
    "dq[0]                  # 返回1（第一个元素）\n",
    "dq[-1]                 # 返回5（最后一个元素）\n",
    "\n",
    "# 检查元素是否存在\n",
    "3 in dq                # 返回True\n",
    "\n",
    "# 旋转操作（非常有用的功能）\n",
    "dq.rotate(1)           # 向右旋转1位，变为[5, 1, 2, 3, 4]\n",
    "dq.rotate(-2)          # 向左旋转2位，变为[2, 3, 4, 5, 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc65ec8e",
   "metadata": {},
   "source": [
    "# 4. 实际应用场景\n",
    "## 4.1 实现队列（FIFO - 先进先出"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0c971dc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "queue = deque()\n",
    "# 入队\n",
    "queue.append(\"任务1\")\n",
    "queue.append(\"任务2\")\n",
    "# 出队\n",
    "while queue:\n",
    "    task = queue.popleft()\n",
    "    print(f\"处理任务: {task}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0967f279",
   "metadata": {},
   "source": [
    "## 4.2 实现栈（LIFO - 后进先出）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aef34d41",
   "metadata": {},
   "outputs": [],
   "source": [
    "stack = deque()\n",
    "# 入栈\n",
    "stack.append(\"数据1\")\n",
    "stack.append(\"数据2\")\n",
    "# 出栈\n",
    "while stack:\n",
    "    data = stack.pop()\n",
    "    print(f\"取出数据: {data}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0551ca54",
   "metadata": {},
   "source": [
    "## 4.3 滑动窗口实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23153d5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 计算列表中每个长度为3的子列表的和\n",
    "data = [1, 2, 3, 4, 5, 6]\n",
    "window = deque(maxlen=3)  # 设置最大长度\n",
    "window_sums = []\n",
    "\n",
    "for num in data:\n",
    "    window.append(num)\n",
    "    if len(window) == 3:\n",
    "        window_sums.append(sum(window))\n",
    "\n",
    "# window_sums = [6, 9, 12, 15]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv (3.13.5)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
